//
// Created by Administrator on 2021/4/6.
//
/*
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明:叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3
/ \
  9  20
/  \
   15   7
返回它的最大深度3 。

        作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xoh1zg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    int maxDepth(TreeNode *root) { // 递归 自顶向下  dfs
        if (!root) return 0;
//        int leftDepth = maxDepth(root->left);
//        int rightDepth = maxDepth(root->right);
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

class Solution2 {
public:
    int maxDepth(TreeNode *root) {  // 题解 bfs
        if (root == nullptr) return 0;
        queue<TreeNode *> Q;
        Q.push(root);
        int ans = 0; // 结果
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode *node = Q.front();
                Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        }
        return ans;
    }
};

int main() {
//    [3,9,20,null,null,15,7]
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(15);
    auto t3 = TreeNode(20, &t4, &t5);
    auto t2 = TreeNode(9);
    auto t1 = TreeNode(3, &t2, &t3);
    Solution sol = Solution();
    cout << sol.maxDepth(&t1);
    return 0;
}